sortlistmodel: Split the SortItem into 2 arrays
authorBenjamin Otte <otte@redhat.com>
Tue, 21 Jul 2020 01:09:10 +0000 (03:09 +0200)
committerBenjamin Otte <otte@redhat.com>
Wed, 22 Jul 2020 12:30:49 +0000 (14:30 +0200)
commit8c608e9c1c1f6478d2114f9ea7ff60c3b0fb2a44
tree5e5d44704a3d20b518f021cd3eae59b56792e0b5
parent283c3b70dd694e4658eaed7b3967c1d19e424d31
sortlistmodel: Split the SortItem into 2 arrays

Instead of one item keeping the item + its position and sorting that
list, keep the items in 1 array and put the positions into a 2nd array.

This is generally slower while sorting, but allows multiple improvements:

1. We can replace items with keys
   This allows avoiding multiple slow lookups when using complex
   comparisons

2. We can keep multiple position arrays
   This allows doing a sorting in the background without actually
   emitting items-changed() until the array is completely sorted.

3. The main list tracks the items in the original model
   So only a single memmove() is necessary there, while the old version
   had to upgrade the position in every item.
Benchmarks:

        sorting a model of simple strings
                          old      new
        256,000 items   256ms    268ms
        512,000 items   569ms    638ms

        sorting a model of file trees, directories first, by size
                          old      new
         64,000 items   350ms    364ms
        128,000 items   667ms    691ms

        removing half the model
                          old      new
        512,000 items    24ms     15ms
      1,024,000 items    49ms     25ms
gtk/gtksortlistmodel.c
testsuite/gtk/sortlistmodel.c